package pers.qianyu.month_202101.date_20210127;

import java.util.*;

/**
 * 剑指 Offer 31. 栈的压入、弹出序列
 * https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
 *
 * @author mizzle rain
 * @date 2021年1月27日12:02:16
 */
public class ValidateStackSequences {
    // 模拟：遍历数组2，遇到一个数不在栈顶，就将这个数前面的数全加入栈中
    public boolean validateStackSequences(int[] arr1, int[] arr2) {
        int m = arr1.length, n = arr2.length;
        if (m == 0 && n == 0) return true;
        if (m != n) return false;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < m; i++) map.put(arr1[i], i);
        Deque<Integer> st = new LinkedList<>();
        int index = 0;
        for (int cur : arr2) {
            if (st.isEmpty() || st.getLast() != cur) {
                int t = map.get(cur);
                for (int j = index; j <= t; j++) {
                    st.addLast(arr1[j]);
                }
                index = t + 1;
                if (st.getLast() != cur) {
                    return false;
                } else {
                    st.pollLast();
                }
            } else st.pollLast();
        }
        return true;
    }

    // 模拟：遍历数组1，一边将数组1的数加入栈中，一边判断数组2 最开始的数是不是和栈顶元素相等，如果相等就出栈
    public boolean validateStackSequences2(int[] arr1, int[] arr2) {
        int m = arr1.length, n = arr2.length;
        if (m != n) return false;
        Deque<Integer> st = new LinkedList<>();
        int index = 0;
        for (int num : arr1) {
            st.addLast(num);
            while (!st.isEmpty() && st.getLast() == arr2[index]) {
                st.pollLast();
                index++;
            }
        }
        return st.isEmpty();
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5}, arr2 = {4, 5, 3, 2, 1};
        boolean result = new ValidateStackSequences().validateStackSequences(arr1, arr2);
        System.out.println("result = " + result);
    }
}